public class MyLinkedList implements IList {
    static class ListNode{
        int val;
        ListNode next;
        ListNode prev;
        ListNode(){

        }
        ListNode(int val){
            this.val = val;
        }
    }
    ListNode head = new ListNode();
    ListNode last;

    @Override
    public void createList() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        head.next = n1;
        n1.next=n2;
        n2.next=n3;
        n1.prev=head;
        n2.prev=n1;
        n3.prev=n2;
        last = n3;
    }

    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(head.next==null){
            head.next=node;
            last = node;
        }else {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }
    }

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head.next==null){
            head.next=node;
            last = node;
        }else {
            node.prev = last;
            last.next = node;
            last = last.next;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        try{
            if(index<0||index>size())
                throw new IndexException("非法下标!");
            if(index==0){
                addFirst(data);
                return;
            }
            if(index==size()){
                addLast(data);
                return;
            }
            ListNode cur = head.next;
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
            ListNode node = new ListNode(data);
            node.prev = cur.prev;
            node.next = cur;
            cur.prev.next = node;
            cur.prev = node;
        }catch(IndexException e){
            e.printStackTrace();
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur!=null){
            if(cur.val==key)
                return true;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        ListNode cur = head.next;
        while(cur!=null){
            if(last.val==key){
                last.prev.next=last.next;
                last=last.prev;
                return;
            }
            if(cur.val==key){
                cur.prev.next=cur.next;
                if(head.next !=null)
                    cur.next.prev=cur.prev;
                return;
            }
            cur=cur.next;
        }
    }

    @Override
    public void removeAllKey(int key) {
        ListNode cur = head.next;
        while(cur!=null){
            if(last.val==key){
                last.prev.next=last.next;
                last=last.prev;
            }
            if(cur.val==key){
                cur.prev.next=cur.next;
                if(head.next !=null)
                    cur.next.prev=cur.prev;
            }
            cur=cur.next;
        }
    }

    @Override
    public int size() {
        int cnt=0;
        ListNode cur = head;
        while(cur!=null){
            cnt++;
            cur=cur.next;
        }
        return cnt;
    }

    @Override
    public void clear() {
        ListNode cur = head.next;
        while(cur != null){
            ListNode curN = cur.next;
            cur.val = 0;
            cur.next=null;
            cur.prev=null;
            cur = curN;
        }
        head=null;
        last=null;
    }

    @Override
    public void display() {
        ListNode cur = head.next;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println(" ");
    }
}
